package com.salim.leetcode.$57;

public class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length==0){
            return new int[][]{newInterval};
        }
        if(newInterval.length==0){
            return intervals;
        }
        int baseIndex = 0;
        for(int i=0;i<intervals.length+1;i++){
            if(i==intervals.length){
                baseIndex = intervals.length;
                break;
            }
            if(intervals[i][0]<newInterval[0]){
                continue;
            }else{
                baseIndex = i;
                break;
            }
        }
        int merged = 0;
        //往左合并
        for(int i=baseIndex-1;i>=0;i--){
            if(intervals[i][0]<=newInterval[1] && intervals[i][1]>=newInterval[0]){
                newInterval[0] = Math.min(intervals[i][0],newInterval[0]);
                newInterval[1] = Math.max(intervals[i][1],newInterval[1]);
                intervals[i][0] = -1;
                intervals[i][1] = -2;
                merged++;
            }else{
                break;
            }
        }
        //往右合并
        for(int i=baseIndex;i<intervals.length;i++){
            if(intervals[i][0]<=newInterval[1] && intervals[i][1]>=newInterval[0]){
                newInterval[0] = Math.min(intervals[i][0],newInterval[0]);
                newInterval[1] = Math.max(intervals[i][1],newInterval[1]);
                intervals[i][0] = -1;
                intervals[i][1] = -2;
                merged++;
            }else{
                break;
            }
        }
        int[][] result = new int[intervals.length-merged+1][2];
        int resultIndex = 0;
        boolean inserted= false;
        if(merged!=0){
            for(int i=0;i<intervals.length;i++) {
                if (intervals[i][0] == -1 && intervals[i][1] == -2) {
                    if (inserted) {
                        continue;
                    } else {
                        inserted = true;
                        result[resultIndex][0] = newInterval[0];
                        result[resultIndex][1] = newInterval[1];
                        resultIndex++;
                        continue;
                    }
                } else {
                    result[resultIndex][0] = intervals[i][0];
                    result[resultIndex][1] = intervals[i][1];
                    resultIndex++;
                }
            }
        }else {
            for(int i=0;i<intervals.length;i++) {
                if(i==baseIndex){
                    inserted = true;
                    result[resultIndex][0] = newInterval[0];
                    result[resultIndex][1] = newInterval[1];
                    resultIndex++;
                    baseIndex=-1;
                    i--;
                }else{
                    if(inserted){
                        result[resultIndex][0] = intervals[i][0];
                        result[resultIndex][1] = intervals[i][1];
                    }else{
                        result[resultIndex][0] = intervals[i][0];
                        result[resultIndex][1] = intervals[i][1];
                    }
                    resultIndex++;
                }
            }
            if(!inserted){
                result[result.length-1][0] = newInterval[0];
                result[result.length-1][1] = newInterval[1];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        InsertInterval i = new InsertInterval();
        //i.insert(new int[][]{{1, 3},{6,9}},new int[]{2,5});
        i.insert(new int[][]{{1, 5}},new int[]{0,0});
    }
}
